package linkedList;


import java.util.HashMap;
import java.util.Stack;

/**
 * @program: data_structures_algorithms
 * @description: 判断链表中是否有环
 * @author: lld
 * @create: 2020-11-14 16:41
 **/
public class Demo1 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node3;
        System.out.println(isCycle(node1) == null ? false : true);
        System.out.println(cycleLength(node1));
        System.out.println(getCycleNode(node1));
    }

    /**
     * @Description: 判断是否有环
     * @Param: [head]
     * @return: 有返回两指针相遇的结点
     **/
    public static Node isCycle(Node head) {
        Node p1 = head;//每次走一步
        Node p2 = head;//每次走两步
        while (head != null && head.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
            if (p1 == p2) {//相遇
                return p1;
            }
        }
        return null;
    }

    /**
     * @Description: 环的长度，相遇结点再相遇的长度
     * @Param: [head]
     * @return: int
     **/
    public static int cycleLength(Node head) {
        if (head == null) {
            return 0;
        }
        Node meetNode = isCycle(head),//相遇结点
                cur = meetNode;
        int length = 0;
        while (cur != null) {
            cur = cur.next;
            length++;
            if (cur == meetNode) {
                return length;
            }
        }
        return 0;
//new HashMap();
    }
    /**
     * @Description: 获取入环结点
     * 只要把其中一个指针放回到头节点位置，另一个指针保持在首次相 遇点，两个指针都是每次向前走1步。那么，它们最终相遇的节点，就是入环节点。
     * @Param: [head]
     * @return: linkedList.Demo1.Node
     **/
    public static Node getCycleNode(Node head) {
        if (head == null) {
            return null;
        }
        Node p1 = isCycle(head);//相遇结点
        Node p2 = head;//头结点
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
            if (p1 == p2) {
                return p1;
            }
        }
        return null;
    }

    private static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
        }

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "data=" + data +
                    '}';
        }
    }
}
